﻿// 2344. 使数组可以被整除的最少删除次数.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;


/*
https://leetcode.cn/problems/minimum-deletions-to-make-array-divisible/description/
给你两个正整数数组 nums 和 numsDivide 。你可以从 nums 中删除任意数目的元素。
请你返回使 nums 中 最小 元素可以整除 numsDivide 中所有元素的 最少 删除次数。如果无法得到这样的元素，返回 -1 。
如果 y % x == 0 ，那么我们说整数 x 整除 y 。


示例 1：
输入：nums = [2,3,2,4,3], numsDivide = [9,6,9,3,15]
输出：2
解释：
[2,3,2,4,3] 中最小元素是 2 ，它无法整除 numsDivide 中所有元素。
我们从 nums 中删除 2 个大小为 2 的元素，得到 nums = [3,4,3] 。
[3,4,3] 中最小元素为 3 ，它可以整除 numsDivide 中所有元素。
可以证明 2 是最少删除次数。

示例 2：
输入：nums = [4,3,6], numsDivide = [8,2,6,10]
输出：-1
解释：
我们想 nums 中的最小元素可以整除 numsDivide 中的所有元素。
没有任何办法可以达到这一目的。


提示：
1 <= nums.length, numsDivide.length <= 105
1 <= nums[i], numsDivide[i] <= 109
*/


class Solution {
public:
    int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
    int minOperations(vector<int>& nums, vector<int>& numsDivide) {
        sort(nums.begin(), nums.end());
        int g = 0;
        for (int i = 0; i < numsDivide.size(); i++) {
            g = gcd(numsDivide[i], g);
        }
        for (int i = 0; i < nums.size(); i++) {
            if (g % nums[i] == 0) 
                return i;
        }

        return -1;
    }
};


int main()
{
    Solution s;
    vector<int> a{ 4,3,6 }, b{ 8,2,6,10 };
    s.minOperations(a,b);
}

 